#include<string>
#include<vector>
using namespace std;

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if (s1.length() > s2.length()) return false;
        int nums[26];
        memset(nums, 0, 26 * sizeof(int));
        for (int i = 0; i < s1.length(); ++i) {
            int index = s1[i] - 'a';
            ++nums[index];
        }
        int cpy[26];
        memcpy(cpy, nums, 26 * sizeof(int));
        int count = s1.length();
        for (int i = 0; i < s1.length(); ++i) {
            int index = s2[i] - 'a';
            if (cpy[index] > 0) {
                if (nums[index] > 0)
                    --count;
                --nums[index];
            }
        }
        if (count == 0)
            return true;
        int left = 0, right = s1.length();
        while (right < s2.length()) {
            int index= s2[left++] - 'a';
            if (cpy[index] > 0) {
                ++nums[index];
                if (nums[index] > 0)
                    ++count;
            }
            index = s2[right++] - 'a';
            if (cpy[index] > 0) {
                if (nums[index] > 0)
                    --count;
                --nums[index];
            }
            if (count == 0)
                return true;
        }
        return false;
    }
};

//class Solution {
//public:
//    bool checkInclusion(string s1, string s2) {
//        int nums[26];
//        memset(nums, 0, 26 * sizeof(int));
//        for (int i = 0; i < s1.length(); ++i)
//            ++nums[s1[i] - 'a'];
//        int cpy[26];
//        memcpy(cpy, nums, 26 * sizeof(int));
//        int left = 0, right = 0;
//        while (left<s2.size()) {
//            while (left < s2.size() && nums[s2[left] - 'a'] == 0) ++left;
//            right = left;
//            int count=0;
//            while (right < s2.size()) {
//                int index = s2[right++] - 'a';
//                if (nums[index] == 0) break;
//                ++count;
//                --nums[index];
//            }
//            if (count == s1.length())
//                return true;
//            ++left;
//            if(count>0)
//                memcpy(nums, cpy, 26 * sizeof(int));
//        }
//        return false;
//
//    }
//};

//int main() {
//    Solution sol;
//    sol.checkInclusion("ab", "eidboaoo");
//}